Various systems have been adopted to carry digitally-encoded signals for communication applications, such as, telephone, video, and data services. These systems are often connection-oriented packet mode transmission systems, such as, asynchronous transfer mode (ATM) systems, frame relay systems, X.25 systems, or other transmission systems. Connection-oriented systems (e.g., ATM systems) have been employed in private and public communication systems or networks (e.g., wide area networks (WANs)) to transfer packetized signals (e.g., data cells or protocol data units) across communication lines, such as, telephone lines, cables, optical fibers, air waves, satellite links, or other communication media.
As an example, the ATM system transfers the data cells or units across the ATM system via connections or channels. The data cells can represent voice, sound, video, graphics, data, or combinations thereof for use in computing or communication applications. The connections can be part of a single physical link carrying a number of logical connections or be a single isolated path. The connections are often classified as either virtual channel connections (VCC), or virtual path connections (VPC) and either permanent virtual connections (PVC), or switched virtual connections (SVC). Connections are generally defined by a source and a destination for the data cell.
ATM systems or networks are generally utilized to support the integration of high quality voice, video, and high speed data traffic which can have specific conformance and quality of service (QOS) requirements. A scheduler is employed to properly select connections for transmission in accordance with operational parameters, such as, QOS requirements. The scheduler organizes transmission of data cells associated with the connections to guarantee QOS requirements and protocol conformance at the network ingress point as well as to maximize bandwidth for the communication system.
ATM systems can utilize at least four types of service categories or modes of traffic for transmission of data cells on connections. These four types include the constant bit rate (CBR) mode, the variable bit rate (VBR) mode, the unspecified bit rate (UBR) mode, and the available bit rate (ABR) mode. Each of these modes have somewhat different transmission protocol requirements. For example, the CBR mode requires that a connection be able to send a specific number of cells or bits per second; the CBR mode must have a set end-to-end bandwidth. The CBR mode is often utilized for data sources, such as, voice or video circuits which are susceptible to cell delay variations (CDV). The VBR mode often utilizes a "single leaky bucket" algorithm (e.g., virtual scheduling algorithm) or "dual leaky bucket" algorithm. Although the VBR mode has somewhat more flexible timing requirements than the CBR mode, the VBR mode must meet timing requirements dictated by the single or dual bucket algorithms. The ABR mode requires the sending of data cells in response to feedback from the network.
To appropriately supply and maximize the effectiveness of the transmission of the CBR, UBR, ABR, and VBR modes of traffic on the network, a scheduler controls a segmentation coprocessor (e.g., segmentation and reassembly unit) to direct communication of data cells or data protocol units on the connections. Generally, the scheduler attempts to select particular connections for transmission at particular times to guarantee conformance to traffic contracts and to QOS at network ingress points. This selection process, or scheduling, selects various connections for transmission based upon operational parameters associated with each connection, with feedback from the network, and with traffic mode timing requirements.
Scheduling a large number of connections with particular timing and communication criteria can lead to complex scheduling problems. For example, various connections can need a particular capacity from the network, and the availability of the particular capacity can be impinged by congestion across the network. These scheduling problems can be compounded by the specific requirements of CBR mode, VBR mode, UBR mode, and ABR modes of traffic.
Traditional network scheduling algorithms, such as, Token Ring and Ethernet utilize fairly simplified scheduling algorithms. The algorithms are typically based upon transmission schemes wherein each member of the network gets a fair share of the network bandwidth. These systems cannot handle QOS requirements or the four categories (e.g., CBR mode, VBR mode, UBR mode, and ABR mode) of traffic for ATM systems.
Prior schedulers utilized in ATM systems access a fixed size schedule table to assist time scheduling of connections. The fixed schedule table is comprised of slots, each of which is assigned to particular connections. The scheduler processes each slot one-by-one and transmits the connection assigned to the slot being processed to the network. These prior schedulers are somewhat inflexible and prioritize CBR and VBR modes traffic. Further, the fixed schedule table requires that the CBR modes of traffic be sent a fixed rate or a harmonic of a fixed rate. Further still, these prior schedulers often must send idle cells to maintain the drain rate for the connection.
Other prior schedulers utilize a first-in, first-out (FIFO) memory and a timer (e.g., hardware units) to appropriately send connections across the network. However, the number of hardware units is limited by circuit size design criteria and cannot be dynamically allocated as bandwidth becomes available. Each FIFO and timer must be dedicated to a particular rate of transmission. Therefore, the rates of transmission are limited. Additionally, these prior schedulers cannot prioritize VBR and CBR modes of traffic.
U.S. patent application Ser. No. 08/759,057 filed Dec. 2, 1996, by Lincoln, entitled "Scheduler Utilizing Dynamic Schedule Table" discloses a communication system which dynamically manages and prioritizes modes of traffic. The communication system can be arranged as an asynchronous transfer mode (ATM) system which can efficiently handle the CBR mode of traffic, the VBR mode of traffic, the UBR mode of traffic, and the ABR mode of traffic. Further, both the CBR mode of traffic and the VBR mode of traffic can be handled on a dynamic basis.
Conventional schedulers do not simultaneously support different quality of service connections (e.g., UBR, VBR, ABR) in a tunnel mode. For example, a tunnel mode is utilized to share a portion of the fixed maximum bandwidth among a number of connections. "Tunnelling" underneath the fixed maximum bandwidth is achieved by assigning an arbitrary maximum bandwidth to a group of connections each of which has an individual service contract. The sum of the bandwidth of the feature allows users or customers to advantageously create a network overlying the service providers (e.g., telephone companies) network). Conventional systems only allow UBR connections to utilize a tunnel mode. UBR connections cannot flexibly absorb excess bandwidth and must be processed in a roundrobin fashion.
Thus, there is a need for a scheduler which can support different quality of service connections in a tunnel mode. Additionally, there is a need for a scheduler for an asynchronous transfer mode (ATM) system which can support different service connections (e.g., the VBR mode of traffic and the ABR mode of traffic) within the same tunnel without exceeding tunnel bandwidth. Further still, there is a need for a scheduler which can handle frame relay and ATM service, along with different quality of service connections. As such, use of a fixed maximum bandwidth is maximized.